/**
 * Class CSC-421
 * Instructor: Wilfredo Marrero
 * @author Hyrum Taft, Don Evett
 * @version 6
 * A solution to homework problem 2.
 * Input: The ArrayList data will contain 1 or more Strings
 * Output: An ArrayList containing all the possible orderings of the "three" words. 
 * Each string will be one possible ordering of the input words, with commas seperating the words.
 * The order in which the string appear in the ArrayList is irrevelant as long as there are no repetitions,
 * all orderings are present, and each String has the proper format (a comma seperated list of words)
 */

import java.util.ArrayList;
import java.util.Collections;

/**
 * Contains a method to produce ordered permutations of input with no repeats
 * @author Hyrum Taft, Don Evett
 * @version 6
 */
public class Permutation 
{

	// array list to store final output
	private ArrayList<String> output;
	
	/**
	 * @return ArrayList of String permutations
	 */
	public ArrayList<String> GetOutput()
	{
		return output;
	}
	
	/**
	 * Permutation Constructor
	 */
	public Permutation()
	{
		output = new ArrayList<String>();
	}
		
	/**
	 * Gives all ordered permutations with no repeats given a list of strings
	 * @param inputStrings strings from which to obtain permutation list
	 * @param inputIndex starting index
	 * @param sizeOfInput size of inputStrings
	 */
    public void OrderedPermutationsNoRepeats(ArrayList<String> inputStrings, int inputIndex, int sizeOfInput)
	{
    	
    	if(sizeOfInput <= 1)
    	{
    		output = inputStrings;
    		return;
    	}
    	
    	// if we are on the last element 
		if (inputIndex == sizeOfInput)
		{
			// build permutation set string
			String outString = "";
			for (int indexOfPermutation = 0; indexOfPermutation < sizeOfInput; indexOfPermutation++)
			{
				if (indexOfPermutation != sizeOfInput -1)
				{
					outString += inputStrings.get(indexOfPermutation) + ",";
				}
				else
				{
					outString += inputStrings.get(indexOfPermutation);
				}
			}
			// add permutation set to the output
			output.add(outString);
		}
		else // we need to find all of the permutations
		{
			for (int i = inputIndex; i < sizeOfInput; i++)
			{
				// fix input string and swap
				String temp = inputStrings.get(inputIndex);
				Collections.swap(inputStrings, inputIndex, i);
				inputStrings.set(i,temp);
				
				// make the problem shorter
				OrderedPermutationsNoRepeats(inputStrings, inputIndex + 1, sizeOfInput);
				
				// now swap back
				temp = inputStrings.get(inputIndex);
				Collections.swap(inputStrings, inputIndex, i);
				inputStrings.set(i, temp);
			}
		}
	}
}
